Unique binary search trees II

Time: O(4N/N(3/2); Space: O(4N/N(3/2); medium

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example 1:

Input: n = 3

Output:

[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]

Explanation:

  • The above output corresponds to the 5 unique BST’s shown below:

    1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

[1]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def __repr__(self):
        if self:
            serial = []
            queue = [self]

            while queue:
                cur = queue[0]

                if cur:
                    serial.append(cur.val)
                    queue.append(cur.left)
                    queue.append(cur.right)
                else:
                    serial.append("#")

                queue = queue[1:]

            while serial[-1] == "#":
                serial.pop()

            return repr(serial)

        else:
            return None

[2]:

class Solution1(object):
    """
    Time: O(4^N/N^(3/2))~=CatalanNumbers
    Space: O(4^N/N^(3/2))~=CatalanNumbers
    """
    def generateTrees(self, n):
        return self.generateTreesRecu(1, n)

    def generateTreesRecu(self, low, high):
        result = []
        if low > high:
            result.append(None)

        for i in range(low, high + 1):
            left = self.generateTreesRecu(low, i - 1)
            right = self.generateTreesRecu(i + 1, high)

            for j in left:
                for k in right:
                    cur = TreeNode(i)
                    cur.left = j
                    cur.right = k
                    result.append(cur)

        return result

[12]:

s = Solution1()
n = 3
# print(s.generateTrees(n)) # [[1, '#', 2, '#', 3], [1, '#', 3, 2], [2, 1, 3], [3, 1, '#', '#', 2], [3, 2, '#', 1]]
# assert s.generateTrees(n) == [
#     [1, '#', 2, '#', 3],
#     [1, '#', 3, 2],
#     [2, 1, 3],
#     [3, 1, '#', '#', 2],
#     [3, 2, '#', 1]
# ]